# 经典区间二分，这里有重复的数，说明有一个区间上的数多了（二分的不是数组下标，而是一个区间），不断分治这个区间，找到答案即可
# 现场想不出来就写hash

class Solution:
    def duplicateInArray(self, nums):
        l,r = 1,len(nums) - 1
        while l < r:
            mid = (l + r) >> 1
            s = 0
            for num in nums:
                if num >= l and num <= mid: s += 1
            if s > mid - l + 1: r = mid
            else: l = mid + 1
        return l